Compilers, in general, translate human-readable code (typically called source code or programs) into machine-readable code that is executable on a target computing system or code that can be further transformed into executable code. During this translation, many modern compilers perform one or more optimizations that enhance the performance of the executable code as it is executed (also called run) on a target computing system. Performance improvement may include one or more of increasing speed of execution, minimizing, maximizing, or optimizing the consumption of available computing resources of the target computing system such as the number of processors in a multi-processor computing system, memory size, bandwidth, and/or latency, power consumption, etc.
Generally, an important aspect of such compiler optimizations is scheduling the operations of the program such that semantic integrity of the program is maintained, i.e., the logical behavior of the program as expressed by the programmer/software developer is not altered, while scheduling the operations for high-speed execution without violating other specified constraints on the usage of available computing resources. This task, often called scheduling, is performed by the compiler or by a component thereof called a scheduler. The schedulers in many modern compilers can schedule operations for execution by a single processor, by several threads of a single processor, or by two or more processors executing in parallel. The compiler/scheduler may therefore perform one or more transform that can parallelize the code. Alternatively, or in addition, the compiler/scheduler can transform the code to optimize temporal and/or spatial locality of data, communication between memory hierarchies (e.g., between a global memory and a private or shared memory of a processor, between shared memories of different processors, etc.), power consumption, etc. Examples of such transforms include loop fusion, loop permutation, loop fission, tiling, etc.
During the course of performing such program transformations, the compiler/scheduler may perform variable expansion, also known as array expansion. Due to variable expansion, the memory requirement of a program variable or a data structure can increase by one or more orders of magnitude, e.g., from a few bytes to tens, hundreds, or even millions of bytes. In some cases, the required memory exceeds the available memory, making the execution of the program on the target computing system infeasible. To prevent this, some compilers/schedulers optimize the overall memory usage of the program during compilation/scheduling. Additionally or in the alternative, some compilers/schedulers perform array compression/contraction, that can decrease the overall memory usage. U.S. Pat. No. 8,572,595 to Lethin et al., entitled “Methods and Apparatus for Aggressive Scheduling in Source Code Compilation,” the entire contents of which are incorporated herein by reference, describes schedulers that can optimize overall memory usage. These techniques, however, do not specifically take into consideration the particular memory requirements of one or more program variables as one or more program transformations are explored. This can lead to implementation of schedules that are inefficient or infeasible in terms of memory usage.